package demo1;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-01
 * Time: 21:30
 */

public class BinarySearchTree {

    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    public TreeNode root;//根节点

    public boolean insert(int key){
         if(root==null){
             root = new TreeNode(key);
         }else {
             TreeNode cur = root;
             TreeNode parent = null;
             TreeNode node = new TreeNode(key);
             while(cur!=null){
                 if(cur.val>key){
                 //根节点大于我们要插入的值，说明这个值应该插入根节点的左边
                     parent = cur;
                     cur = cur.left;
                 }else if(cur.val<key) {
                // 根节点小于我们要插入的值，说明这个值应该插入根节点的右边
                     parent = cur;
                     cur = cur.right;
                 }else{
                     //二叉搜索树中不能出现相同的元素
                     return false;//插入失败
                 }
             }
             //此时证明cur为空，已经找到了插入的位置
             if(parent.val>key){
                 parent.left = node;
             }else {
                 parent.right = node;
             }
         }
         return true;
    }

    public int search(int key){
        if(root==null){
            return -1;//没有节点不能查找
        }
        TreeNode cur = root;
        while(cur!=null){
            if(cur.val>key){
                cur = cur.left;
            }else if(cur.val<key){
                cur = cur.right;
            }else {
                return cur.val;//找到了将这个值返回去
            }
        }
        return -1;//在这颗二叉搜索树中没有找到
    }

    public void removeNode(TreeNode cur,TreeNode parent){
        //cur.left==null
        if(cur.left==null){
            if(root==cur){
                root = root.right;
            }else if(parent.right ==cur) {
                parent.right = cur.right;
            }else {
                parent.left = cur.right;
            }

        }else if(cur.right==null){
             if(root==cur){
                 root=root.left;
             }else if(parent.right==cur){
                 parent.right = cur.left;
             }else {
                 parent.left = cur.left;
             }
        }else {
             //都不为空采用节点替换法
            //可以采用cur左边找最大的节点也就是cur最右边的节点
            //当然也可以去cur右边找最小的节点cur最左边的节点
            TreeNode targetParent =cur;
            TreeNode target = cur.left;
            while(target.right!=null){
                targetParent = target;
                target = target.right;
            }
            cur.val = target.val;
            if(targetParent.right==target){
                targetParent.right = target.left;
            }else {
                targetParent.left = target.left;
            }
        }

    }

    public boolean remove(int key){
        if(root==null){
            return false;//没有节点不能查找
        }
        TreeNode cur = root;
        TreeNode parent = null;
        TreeNode node = new TreeNode(key);
        while(cur!=null){
            if(cur.val>key){
                parent = cur;
                cur = cur.left;
            }else if(cur.val<key){
                parent = cur;
                cur = cur.right;
            }else {
                //找到这个要删除的节点了
                removeNode(cur,parent);
                return true;
            }
        }
        return false;
    }




}
